package com.since.algorithm.linkedlist;


/**
 * Created by Sincerity on 2020/5/8.
 * 描述：链表相关的算法
 * 1. 排序后的链表相加 {@link #addTwoNumbers(ListNode, ListNode)}
 */
class LinkedAlgorithm {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        LinkedAlgorithm linked = new LinkedAlgorithm();

        System.out.println(linked.addTwoNumbers(l1, l2));
    }

    /**
     * 回文联表
     *
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        //如果链表是单数 就不是回文链表
        int size = getEffectiveNode(head);
        if (head.next == null) return false;
        if (size % 2 == 1) {
            return false;
        }
        ListNode reverseHead = reverseLinkedList(head);
        ListNode temp = head;
        ListNode rever = reverseHead;
        boolean isSame = false;
        while (temp != null) {
            isSame = temp.val == rever.val;
            temp = temp.next;
            rever = rever.next;
        }
        return isSame;
    }

    private ListNode reverseLinkedList(ListNode head) {
        //1.思路 新建一个链表 2.遍历旧链表 每遍历一个节点 3.就把这个节点插入到新链表的第一个位置
        ListNode newEntry = new ListNode(0);
        ListNode temp = head.next;
        ListNode next;
        while (temp != null) {
            //最好画个图自己详细理解一下
            //得到临时指针节点的下一个节点 ,为什么要得到临时指针的下一个节点
            // 因为下面会把这个临时指针和临时指针的next节点改变指向
            next = temp.next;
            //临时指针的一个节点变成新链表的头节点
            temp.next = newEntry.next;
            //让这个节点断掉和head节点的指针 从而把新链表的下一个位置指向这个临时节点 变成一个新的链表
            newEntry.next = temp;
            //因为在上一步已经断掉了temp和head的指向关系 所以这时候将前面保存的next值重新付给temp 让temp和head重新关联
            temp = next;
        }
        //为了保证是同一个链表 将指针重新指向新链表的第一个节点
        return newEntry.next;

    }

    private int getEffectiveNode(ListNode head) {
        int length = 0;
        if (head.next == null) return length;
        while (head.next != null) {
            length++;
            head = head.next;
        }
        return length;
    }

    /**
     * 二个链表的节点相加
     *
     * @param l1 链表1
     * @param l2 链表1
     * @return 相加之后的链表
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return null;
        }
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            int sum = x + y + carry;
            carry = sum / 10;
            sum = sum % 10;
            cur.next = new ListNode(sum);

            cur = cur.next;
            if (l1 != null)
                l1 = l1.next;
            if (l2 != null)
                l2 = l2.next;
        }
        if (carry == 1) {
            cur.next = new ListNode(carry);
        }
        showList(pre);
        return pre.next;

    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    '}';
        }
    }

    private void showList(ListNode head) {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        ListNode temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }
}
